Queue = Queue or {}

function Queue.new()
    local inst = {
        _cname = "lang.Queue",
    }
    
    local arr = {}
    local head = 1
    local len = 0
    
    function inst:count()
        return len
    end
    
    local function getForLoopTail()
        return head + len - 1
    end
    
    function inst:clear()
        for i=head,getForLoopTail() do
            arr[i] = nil
        end
        head = 1
        len = 0
    end
    
    function inst:contains(v)
        for i=head,getForLoopTail() do
            if arr[i] == v then
                return true
            end
        end
        return false
    end
    
    function inst:enqueue(v)
        arr[head + len] = v
        len = len + 1
    end
    
    function inst:dequeue()
        local forLoopTail = getForLoopTail()
        assert(head <= forLoopTail, "Queue: dequeue: out of range")
        local v = arr[head]
        arr[head] = nil
        head = head + 1
        len = len - 1

        if 0 == len then
            head = 1
        else
            if head >= 8 and head / forLoopTail >= 0.5 then
                local j = 1
                for i=head,forLoopTail do
                    arr[j] = arr[i]
                    j = j + 1
                end
                for i=j,forLoopTail do
                    arr[i] = nil
                end
                head = 1
            end
        end
        return v
    end
    
    function inst:peek()
        local v = arr[head]
        return v
    end
    
    function inst:copyTo(dst)
        assert("table" == type(dst), "copyTo: dst not table or Stack")
        if "lang.Queue" == dst._cname then
            for i=head,getForLoopTail() do
                dst:enqueue(arr[i])
            end
        else
            for i=head,getForLoopTail() do
                table.insert(dst, arr[i])
            end
        end
    end
    
    function inst:__tostring()
        if len <= 0 then return "" end
        local strTb = {}
        for i=head,getForLoopTail() do
            local item = arr[i]
            table.insert(strTb, (nil == item) and "nil" or tostring(item))
        end
        return table.concat(strTb, ",")
    end

    function inst:__len()
        return len
    end
    
    function inst:__index(k)
        error("Queue: invalid member: " .. k)
    end
    
    function inst:__newindex(k, v)
        error("Queue: add member error: " .. k)
    end
    
    setmetatable(inst, inst)
    return inst
end

function Queue.__call()
    return Queue.new()
end
setmetatable(Queue, Queue)


local function Test1()
    local q = Queue()
    assert(0 == q:count(), "count error")
    
    q:enqueue("one")
    assert(1 == q:count(), "enqueue error")
    assert("one" == q:peek(), "peek error")
    assert(true == q:contains("one"), "contains error")
    assert(false == q:contains("1"), "contains error")
    
    q:enqueue("two")
    assert(2 == q:count(), "enqueue error")
    assert("one" == q:peek(), "peek error")
    assert(true == q:contains("one"), "contains error")
    assert(true == q:contains("two"), "contains error")
    assert(false == q:contains("1"), "contains error")
    
    assert("one" == q:dequeue(), "dequeue error")
    assert(1 == q:count(), "enqueue error")
    assert("two" == q:dequeue(), "dequeue error")
    assert(0 == q:count(), "enqueue error")
    assert(nil == q:peek(), "dequeue error")
    --q:dequeue() --error
    
    local q2 = Queue()
    q2:enqueue("1")
    q:enqueue("a")
    q:copyTo(q2)
    assert("1" == q2:dequeue(), "dequeue error")
    assert(1 == q2:count(), "enqueue error")
    assert("a" == q2:dequeue(), "dequeue error")
    assert(0 == q2:count(), "enqueue error")
    assert(nil == q2:peek(), "dequeue error")
end

Test1()


